
//3011.判断一个数组是否可以变成有序
class Solution {
    //计算二进制位中1的个数
    int setbit(int n)
    {
        int count = 0;
        while (n)
        {
            n = n & (n - 1);
            count++;
        }
        return count;
    }

public:
    bool canSortArray(vector<int>&  nums) {
        int pre_max = 0;  //记录上一个最小值
        int n = nums.size(), i = 0;
        while (i < n )
        {
            int start = setbit(nums[i]);  //记录开始位置的二进制位个数
            int in_max = 0;
            while (i < n && setbit(nums[i]) == start)
            {
                if(nums[i]<pre_max) return false;  //判断当前位置元素大小是否比上一组最大元素大
                in_max = max(in_max, nums[i]);  //记录该组元素最大值
                i++;
            }
            pre_max = in_max;
        }
        return true;
    }
};